Geometric Structures: Problem Set D (Basic Graph Theory)
Prepared by:
Joseph Malkevitch
Department of Mathematics and Computer Studies
York College (CUNY)
Jamaica, New York
email:
malkevitch@york.cuny.edu
web page:
http://york.cuny.edu/~malk/
Graphs are a fascinating tool for problem solving and for geometric explorations. I will use the graph concept as an organizing idea to consider a broad array of topics in geometry: polyhedra, polygons, tilings, lattice point problems, symmetry, and models for different types of finite geometries.
When there are no explicit restrictions on how to draw your graph(s), where possible draw the graph diagrams without loops and multiple edges and as connected plane graphs.
The degree or valence of a vertex v in a graph (without loops) is the number of edges at v. If there are loops at v each loop contributes 2 to the valence of v. One can think of the the valence of v as the "local" number of "curves" that meet at v.
A graph is connected if for any pair of vertices u and v one can get from u to v by moving along the edges of the graph. Such routes that move along edges are known by different names: edge progressions, paths, simple paths, walks, trails, circuits, cycles, etc. The usual difference between the terms is whether the routes repeat vertices other than the start vertex, repeat edges, etc. When neither vertices nor edges are repeated in an a "route" of edges in a graph it is known as a path.
A graph is called plane if it can be drawn in the plane so that edges meet only at vertices. Some drawings of graphs in the plane have edges that meet at points other than vertices but these "accidental crossings" can be eliminated using a different drawing. A graph which has the potential to be drawn as a plane graph is known as a planar graph. One talks about the embedding of a graph in the plane and some graphs have embeddings where edges meet only at the vertices. Here is an example of a planar graph which has not been displayed as a plane graph.
One can redraw the edges 06 and 15 indifferent positions so that the crossings which occur at points other than vertices are avoided.
0.
a. Write down the valences of the 16 vertices in the graph below:
b. Draw another graph which is not isomorphic to this one which is plane and has 16 vertices.
1. Is there a connected graph whose valences are:
a. 5, 3, 2, 2, 2, 1, 1
b. 8, 6, 4
c. 5, 5, 3, 3, 3, 2, 2, 2, 2, 2, 2
d. 5, 3, 3, 3, 2, 2, 2, 2, 2
e. 4, 4, 4, 4, 4, 4, 4, 4, 4
2. Draw as many connected graphs whose vertices have valences:
5, 3, 2, 2, 2, 1, 1
as you can and which have no loops or multiple edges and are non-isomorphic.
3. Can you find a connected graph whose degrees are without loops or multiple edges:
4, 4, 4, 4, 4
Can you draw this graph in the plane so that edges meet only at vertices?
4. For the graph below:
a. A snow plow starts at vertex 0 and must return to vertex 0 using a route which visits each edge at least once and repeats a minimum number of edges. Find such a route and how many repeated edges does it have?
Assume that the edges all have the length, say length 1.
b. Repeat doing question a. under the assumption that vertical edges have length 1, horizontal edges have length 5, and the "diagonal edges" have length 3.
5. For the graph below:
a. What is the shortest route from 0 to 3? What is the shortest route from 0 to 8? (Route length is the sum of the weights of the edges in the route. When no weight is assigned to an edge the weight is assumed to be 1.)
b. What is the shortest route from 5 to 2? What is the shortest route from 5 to 5 to 2?
c. What is the shortest route from 7 to 2? From 7 to 0?
6. a. Can you draw a plane connected graph with valences 1, 2, 3?
b. Can you draw a plane connected graph with valences 1, 2, 3, 4?
c. Can you draw a plane connected graph with valences, 1, 2, 3, 4, 5?
d. Can you draw a plane connected graph with valences 1, 2, 3, 4, 5, 6?
e. Can you draw a plane connected graph with valences, 1, 3, 5, 7, 9, and 11?
7. Redraw the graph below as a plane graph.
